class Solution {
public:
    int dp[105][105];
    int minDistance(vector<int>& houses, int k) {
        houses.insert(houses.begin(), 0);
        if (k == houses.size()) return 0;
        sort(houses.begin(), houses.end());
        for (int i = 1; i < houses.size(); i++) dp[i][0] = 100000000;
        for (int i = 1; i < houses.size(); i++)
        {
            for (int j = 1; j <= k; j++)
            {
                dp[i][j] = 100000000;
                int pos = i;
                int temp = 0;
                for (int m = i; m >= 1; m--)
                {
                    int num = (i - m + 2) / 2;
                    if (m + num - 1 != pos)
                    {
                        temp += houses[pos] - houses[m + num - 1];
                        pos -= 1;
                    }
                    temp += houses[pos] - houses[m];
                    dp[i][j] = min(dp[i][j], dp[m - 1][j - 1] + temp);
                }
            }
        }
        return dp[houses.size() - 1][k];
    }
};